#include "lexer.h"
#include <fstream>      // 文件流操作
#include <sstream>      // 字符串流操作
#include <cctype>       // 字符处理函数
#include <queue>        // 队列数据结构
#include <algorithm>    // 算法库
#include <regex>        // 正则表达式支持

// DFA实现 - 确定有限自动机
DFA::DFA() : startState(0) {}  // 构造函数，初始化起始状态为0

// 添加状态到DFA中，可选择是否为接受状态
void DFA::addState(int state, bool isAccepting) {
    states.insert(state);  // 将状态添加到状态集合中
    if (isAccepting) {
        acceptingStates.insert(state);  // 如果是接受状态，添加到接受状态集合
    }
}

// 添加从一个状态到另一个状态的转换，基于给定的输入符号
void DFA::addTransition(int from, int to, char symbol) {
    transitions[{from, symbol}] = to;  // 存储转换关系
}

// 根据当前状态和输入符号确定下一个状态
int DFA::transition(int state, char symbol) const {
    auto it = transitions.find({state, symbol});  // 查找转换
    return it != transitions.end() ? it->second : -1;  // 返回下一状态，如果不存在则返回-1
}

// 检查给定状态是否为接受状态
bool DFA::isAccepting(int state) const {
    return acceptingStates.find(state) != acceptingStates.end();  // 在接受状态集合中查找
}

// 设置DFA的起始状态
void DFA::setStartState(int state) {
    startState = state;
}

// 获取DFA的起始状态
int DFA::getStartState() const {
    return startState;
}

// NFA实现 - 非确定有限自动机
NFA::NFA() : startState(0) {}  // 构造函数，初始化起始状态为0

// 添加状态到NFA中，可选择是否为接受状态
void NFA::addState(int state, bool isAccepting) {
    states.insert(state);  // 将状态添加到状态集合中
    if (isAccepting) {
        acceptingStates.insert(state);  // 如果是接受状态，添加到接受状态集合
    }
}

// 添加从一个状态到另一个状态的转换，基于给定的输入符号
void NFA::addTransition(int from, int to, char symbol) {
    transitions[{from, symbol}].insert(to);  // 存储转换关系，一个输入可以有多个目标状态
}

// 添加ε转换（无需输入符号的转换）
void NFA::addEpsilonTransition(int from, int to) {
    epsilonTransitions[from].insert(to);  // 存储ε转换关系
}

// 计算状态的ε闭包（可通过ε转换到达的所有状态集合）
std::set<int> NFA::epsilonClosure(int state) const {
    std::set<int> closure = {state};  // 初始包含自身
    std::queue<int> queue;
    queue.push(state);  // 将初始状态加入队列

    // 广度优先搜索所有可通过ε转换到达的状态
    while (!queue.empty()) {
        int current = queue.front();
        queue.pop();

        auto it = epsilonTransitions.find(current);
        if (it != epsilonTransitions.end()) {
            for (int next : it->second) {
                if (closure.insert(next).second) {  // 如果是新状态
                    queue.push(next);  // 加入队列继续搜索
                }
            }
        }
    }

    return closure;  // 返回完整的ε闭包
}

// 计算一组状态在给定输入符号下的转换结果
std::set<int> NFA::move(const std::set<int>& states, char symbol) const {
    std::set<int> result;
    for (int state : states) {
        auto it = transitions.find({state, symbol});
        if (it != transitions.end()) {
            result.insert(it->second.begin(), it->second.end());  // 合并所有可能的目标状态
        }
    }
    return result;  // 返回所有可能的下一状态集合
}

// 将NFA转换为等价的DFA（子集构造法）
DFA NFA::toDFA() const {
    DFA dfa;
    std::map<std::set<int>, int> dfaStateMap;  // NFA状态集合到DFA状态的映射
    std::queue<std::set<int>> unprocessed;  // 待处理的NFA状态集合
    
    // 初始状态是NFA开始状态的ε闭包
    std::set<int> initial = epsilonClosure(startState);
    dfaStateMap[initial] = 0;  // 映射到DFA的状态0
    unprocessed.push(initial);
    dfa.addState(0);
    dfa.setStartState(0);

    // 如果初始状态包含NFA的接受状态，则DFA的初始状态也是接受状态
    for (int state : initial) {
        if (acceptingStates.find(state) != acceptingStates.end()) {
            dfa.addState(0, true);
            break;
        }
    }

    // 处理所有待处理的状态集合
    while (!unprocessed.empty()) {
        std::set<int> current = unprocessed.front();
        unprocessed.pop();
        int currentDFAState = dfaStateMap[current];

        // 只对文法中实际出现的字符进行转换
        std::set<char> validChars = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm',
                                    'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z',
                                    'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M',
                                    'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z',
                                    '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
                                    '+', '-', '*', '/', '=', '<', '>', '!', '&', '|', '^', '%',
                                    '{', '}', '(', ')', '[', ']', ';', ',', '_', '.'};  // 添加所有可能的有效字符
        
        for (char c : validChars) {
            std::set<int> next;
            // 计算move结果
            std::set<int> moved = move(current, c);
            // 对move结果中的每个状态计算ε闭包
            for (int state : moved) {
                std::set<int> closure = epsilonClosure(state);
                next.insert(closure.begin(), closure.end());  // 合并所有闭包
            }

            if (!next.empty()) {  // 如果有有效转换
                // 如果这是一个新状态集合
                if (dfaStateMap.find(next) == dfaStateMap.end()) {
                    int newState = dfaStateMap.size();  // 分配新的DFA状态ID
                    dfaStateMap[next] = newState;
                    unprocessed.push(next);  // 加入待处理队列
                    dfa.addState(newState);
                    
                    // 检查是否应该是接受状态（如果包含任何NFA的接受状态）
                    for (int state : next) {
                        if (acceptingStates.find(state) != acceptingStates.end()) {
                            dfa.addState(newState, true);
                            break;
                        }
                    }
                }
                
                // 添加DFA转换
                dfa.addTransition(currentDFAState, dfaStateMap[next], c);
            }
        }
    }

    return dfa;  // 返回构造的DFA
}

// Lexer实现 - 词法分析器
Lexer::Lexer() {
    // 初始化关键字表
    keywords["int"] = "关键字";
    keywords["float"] = "关键字";
    keywords["double"] = "关键字";
    keywords["char"] = "关键字";
    keywords["void"] = "关键字";
    keywords["if"] = "关键字";
    keywords["else"] = "关键字";
    keywords["while"] = "关键字";
    keywords["return"] = "关键字";
    keywords["for"] = "关键字";
    keywords["do"] = "关键字";
    keywords["break"] = "关键字";
    keywords["continue"] = "关键字";
    keywords["switch"] = "关键字";
    keywords["case"] = "关键字";
    keywords["default"] = "关键字";
    keywords["const"] = "关键字";
    keywords["static"] = "关键字";
    keywords["auto"] = "关键字";
    keywords["extern"] = "关键字";
    keywords["register"] = "关键字";
    keywords["sizeof"] = "关键字";
    keywords["typedef"] = "关键字";
    keywords["union"] = "关键字";
    keywords["enum"] = "关键字";
    keywords["struct"] = "关键字";
    keywords["goto"] = "关键字";
    


    // 初始化运算符表
    operators["+"] = "运算符";
    operators["-"] = "运算符";
    operators["*"] = "运算符";
    operators["/"] = "运算符";
    operators["="] = "运算符";
    operators["<"] = "运算符";
    operators[">"] = "运算符";
    operators["=="] = "运算符";
    operators["!="] = "运算符";
    operators["<="] = "运算符";
    operators[">="] = "运算符";
    operators["++"] = "运算符";
    operators["--"] = "运算符";
    operators["+="] = "运算符";
    operators["-="] = "运算符";
    operators["*="] = "运算符";
    operators["/="] = "运算符";
    operators["<<"] = "运算符";
    operators[">>"] = "运算符";
    operators["&"] = "运算符";
    operators["|"] = "运算符";
    operators["^"] = "运算符";
    operators["~"] = "运算符";
    operators["&&"] = "运算符";
    operators["||"] = "运算符";
    operators["!"] = "运算符";


    // 初始化界符表
    delimiters["{"] = "界符";
    delimiters["}"] = "界符";
    delimiters["("] = "界符";
    delimiters[")"] = "界符";
    delimiters[";"] = "界符";
    delimiters[","] = "界符";
    delimiters["["] = "界符";
    delimiters["]"] = "界符";
    delimiters["*/"] = "界符";
    delimiters["/*"] = "界符";
    delimiters["//"] = "界符";

}

Lexer::~Lexer() {}  // 析构函数

// 从文件加载文法规则
void Lexer::loadGrammar(const std::string& grammarFile) {
    std::ifstream file(grammarFile);
    if (!file) {
        throw std::runtime_error("无法打开文法文件");  // 文件打开失败时抛出异常
    }

    std::string line;
    std::vector<std::string> rules;
    
    // 读取所有非空行作为规则
    while (std::getline(file, line)) {
        if (!line.empty()) {
            rules.push_back(line);
        }
    }

    // 为每条规则创建NFA并转换为DFA
    for (const auto& rule : rules) {
        NFA nfa = parseGrammarRule(rule);  // 解析规则生成NFA
        dfaList.push_back(std::make_unique<DFA>(nfa.toDFA()));  // 转换为DFA并存储
    }
}

// 解析文法规则，构建对应的NFA
NFA Lexer::parseGrammarRule(const std::string& rule) {
    std::istringstream iss(rule);
    std::string nonTerminal, arrow, pattern;
    iss >> nonTerminal >> arrow;  // 读取非终结符和箭头
    
    if (arrow != "->") {
        throw std::runtime_error("无效的文法规则格式：" + rule);  // 检查规则格式
    }

    // 读取剩余的模式部分
    std::getline(iss >> std::ws, pattern);
    
    NFA nfa;
    int currentState = 0;
    int nextState = 1;
    nfa.addState(currentState);  // 添加开始状态
    
    // 逐字符解析模式
    for (size_t i = 0; i < pattern.length(); i++) {
        if (pattern[i] == '[') {  // 处理字符类 [a-z]
            i++;  // 跳过 '['
            std::set<char> charClass;
            while (i < pattern.length() && pattern[i] != ']') {
                if (pattern[i] == '-' && i > 0 && i + 1 < pattern.length()) {
                    // 处理范围，如 a-z
                    char start = pattern[i-1];
                    char end = pattern[i+1];
                    for (char c = start; c <= end; c++) {
                        charClass.insert(c);
                    }
                    i += 2;
                } else {
                    charClass.insert(pattern[i++]);
                }
            }
            
            // 为字符类中的每个字符创建转换
            for (char c : charClass) {
                nfa.addTransition(currentState, nextState, c);
            }
            currentState = nextState++;
            nfa.addState(currentState);
        }
        else if (pattern[i] == '(') {  // 处理分组 (a|b)
            size_t groupEnd = pattern.find(')', i);
            if (groupEnd == std::string::npos) {
                throw std::runtime_error("未闭合的括号");  // 检查括号匹配
            }
            
            std::string group = pattern.substr(i + 1, groupEnd - i - 1);
            if (groupEnd + 1 < pattern.length() && pattern[groupEnd + 1] == '*') {
                // 处理 (...)* 结构（Kleene星号，表示0或多次重复）
                int loopStart = currentState;
                int loopEnd = nextState;
                nfa.addState(loopEnd);
                
                // 添加ε转换以跳过循环（0次情况）
                nfa.addEpsilonTransition(loopStart, loopEnd);
                
                // 处理组内的选项（用|分隔的多个选项）
                std::istringstream groupStream(group);
                std::string option;
                while (std::getline(groupStream, option, '|')) {
                    int optionStart = nextState++;
                    nfa.addState(optionStart);
                    nfa.addEpsilonTransition(loopStart, optionStart);  // 从循环开始到选项开始
                    
                    // 为选项中的每个字符创建转换
                    for (char c : option) {
                        if (c != ' ') {
                            int optionEnd = nextState++;
                            nfa.addState(optionEnd);
                            nfa.addTransition(optionStart, optionEnd, c);
                            optionStart = optionEnd;
                        }
                    }
                    nfa.addEpsilonTransition(optionStart, loopStart);  // 从选项结束回到循环开始（多次情况）
                }
                
                currentState = loopEnd;
                i = groupEnd + 1;  // 跳过 '*'
            } else {
                // 处理普通分组（不带*）
                std::istringstream groupStream(group);
                std::string option;
                while (std::getline(groupStream, option, '|')) {
                    int optionStart = currentState;
                    for (char c : option) {
                        if (c != ' ') {
                            nfa.addState(nextState);
                            nfa.addTransition(optionStart, nextState, c);
                            optionStart = nextState++;
                        }
                    }
                }
                i = groupEnd;
            }
        }
        else if (pattern[i] != ' ') {  // 处理普通字符（忽略空格）
            nfa.addState(nextState);
            nfa.addTransition(currentState, nextState, pattern[i]);
            currentState = nextState++;
        }
    }
    
    // 设置最后一个状态为接受状态
    nfa.addState(currentState, true);
    return nfa;
}

// 检查是否是有效的标识符
bool Lexer::isValidIdentifier(const std::string& token) {
    if (token.empty() || !isLetter(token[0])) {
        return false;  // 标识符必须以字母或下划线开头
    }

    // 其余字符必须是字母、数字或下划线
    return std::all_of(token.begin() + 1, token.end(), 
        [this](char c) { return isLetter(c) || isDigit(c); });
}

// 检查是否是有效的整数
bool Lexer::isValidInteger(const std::string& token) {
    if (token.empty()) return false;
    
    size_t start = 0;
    if (token[0] == '+' || token[0] == '-') {
        if (token.length() == 1) return false;  // 只有符号不是有效整数
        start = 1;  // 跳过符号
    }
    
    // 所有剩余字符必须是数字
    return std::all_of(token.begin() + start, token.end(), 
        [this](char c) { return isDigit(c); });
}

// 检查是否是有效的浮点数
bool Lexer::isValidFloat(const std::string& token) {
    std::regex floatPattern(R"([+-]?(\d+\.\d*|\.\d+))");  // 匹配浮点数格式
    return std::regex_match(token, floatPattern);
}

// 检查是否是有效的科学计数法表示
bool Lexer::isValidScientific(const std::string& token) {
    std::regex scientificPattern(R"([+-]?(\d+\.\d*|\.\d+|\d+)[eE][+-]?\d+)");  // 匹配科学计数法格式
    return std::regex_match(token, scientificPattern);
}

// 检查是否是有效的复数表示
bool Lexer::isValidComplex(const std::string& token) {
    std::regex complexPattern(R"([+-]?\d+(\.\d*)?([eE][+-]?\d+)?[+-]\d+(\.\d*)?([eE][+-]?\d+)?i)");  // 匹配复数格式
    return std::regex_match(token, complexPattern);
}

// 获取token的类型
std::string Lexer::getTokenType(const std::string& token) {
    // 按优先级检查各种类型
    // 检查是否是关键字
    if (keywords.find(token) != keywords.end()) {
        return "关键字";
    }

    // 检查是否是运算符
    if (operators.find(token) != operators.end()) {
        return "运算符";
    }

    // 检查是否是界符
    if (delimiters.find(token) != delimiters.end()) {
        return "界符";
    }

    // 检查是否是复数
    if (isValidComplex(token)) {
        return "常数";
    }

    // 检查是否是科学计数法
    if (isValidScientific(token)) {
        return "常数";
    }

    // 检查是否是浮点数
    if (isValidFloat(token)) {
        return "常数";
    }

    // 检查是否是整数
    if (isValidInteger(token)) {
        return "常数";
    }

    // 检查是否是标识符
    if (isValidIdentifier(token)) {
        return "标识符";
    }

    return "未知";  // 无法识别的token类型
}

// 分析源代码文件，生成token序列
std::vector<Token> Lexer::analyze(const std::string& sourceFile) {
    std::vector<Token> tokens;
    std::ifstream file(sourceFile);
    if (!file) {
        throw std::runtime_error("无法打开源代码文件");  // 文件打开失败时抛出异常
    }

    std::string line;
    int lineNumber = 0;
    std::string token;
    
    // 逐行读取源代码
    while (std::getline(file, line)) {
        lineNumber++;
        size_t i = 0;
        
        // 处理每一行中的所有字符
        while (i < line.length()) {
            // 跳过空白字符
            while (i < line.length() && isWhitespace(line[i])) {
                i++;
            }
            if (i >= line.length()) break;

            // 处理注释
            if (i + 1 < line.length() && line[i] == '/' && line[i + 1] == '/') {
                break;  // 跳过行注释
            }

            // 尝试识别复数（使用正则表达式）
            std::string remaining = line.substr(i);
            std::smatch complexMatch;
            if (std::regex_search(remaining, complexMatch, std::regex(R"(^[+-]?\d+(\.\d*)?([eE][+-]?\d+)?[+-]\d+(\.\d*)?([eE][+-]?\d+)?i)"))) {
                tokens.push_back({lineNumber, "常数", complexMatch.str()});
                i += complexMatch.length();
                continue;
            }

            // 尝试识别科学计数法（使用正则表达式）
            if (std::regex_search(remaining, complexMatch, std::regex(R"(^[+-]?(\d+\.\d*|\.\d+|\d+)[eE][+-]?\d+)"))) {
                tokens.push_back({lineNumber, "常数", complexMatch.str()});
                i += complexMatch.length();
                continue;
            }

            // 尝试识别浮点数（使用正则表达式）
            if (std::regex_search(remaining, complexMatch, std::regex(R"(^[+-]?(\d+\.\d*|\.\d+))"))) {
                tokens.push_back({lineNumber, "常数", complexMatch.str()});
                i += complexMatch.length();
                continue;
            }

            // 处理标识符和关键字
            if (isLetter(line[i])) {
                token.clear();
                while (i < line.length() && (isLetter(line[i]) || isDigit(line[i]))) {
                    token += line[i++];
                }
                tokens.push_back({lineNumber, getTokenType(token), token});
                continue;
            }

            // 处理数字（整数）
            if (isDigit(line[i])) {
                token.clear();
                while (i < line.length() && isDigit(line[i])) {
                    token += line[i++];
                }
                tokens.push_back({lineNumber, "常数", token});
                continue;
            }

            // 处理运算符
            if (isOperator(line[i])) {
                std::string op(1, line[i++]);
                // 检查是否是双字符运算符（如 ==, !=, <=, >=）
                if (i < line.length() && isOperator(line[i])) {
                    std::string doubleOp = op + line[i];
                    if (operators.find(doubleOp) != operators.end()) {
                        op = doubleOp;
                        i++;
                    }
                }
                tokens.push_back({lineNumber, "运算符", op});
                continue;
            }

            // 处理界符
            if (isDelimiter(line[i])) {
                std::string delimiter(1, line[i++]);
                tokens.push_back({lineNumber, "界符", delimiter});
                continue;
            }

            // 无法识别的字符
            throw std::runtime_error("词法错误 行号 " + std::to_string(lineNumber) + 
                                   ": 无法识别的字符 '" + std::string(1, line[i]) + "'");
        }
    }

    return tokens;  // 返回所有识别出的token
}

// 检查字符是否是空白字符
bool Lexer::isWhitespace(char c) {
    return c == ' ' || c == '\t' || c == '\n' || c == '\r';
}

// 检查字符是否是字母或下划线
bool Lexer::isLetter(char c) {
    return isalpha(c) || c == '_';
}

// 检查字符是否是数字
bool Lexer::isDigit(char c) {
    return isdigit(c);
}

// 检查字符是否是运算符
bool Lexer::isOperator(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/' || 
           c == '=' || c == '<' || c == '>' || c == '!' ||
           c == '&' || c == '|' || c == '^' || c == '%';
}

// 检查字符是否是界符
bool Lexer::isDelimiter(char c) {
    return c == '{' || c == '}' || c == '(' || c == ')' || 
           c == ';' || c == ',' || c == '[' || c == ']';
}